#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Miguel Silva, 6311
Estrutura de Dados e Algoritmos
Engenharia Informática 
2012/2013
"""

class MergesortClass(object):
	"""
	Classe utilizada para representação do algoritmo de 
	ordenação Mergesort.
	"""

	def __init__(self):
		"""
		Constructor da classe MergesortClass.
		"""
		super(MergesortClass, self).__init__()
	
	def merge_sort(self,list, p, r):
		"""
		Função que divide a lista em sublistas de forma recursiva e,
		chama a função merge que intercala as sublistas de forma ordenada.

		Argumentos:
		list -- lista
		p -- posição inicial
		r -- tamanho da lista
		"""
		if p < r:
			q = (p + r ) / 2	# calculo do indice para divisão da lista em duas sublistas
			self.merge_sort(list, p, q)
			self.merge_sort(list, q+1, r)
			self.merge(list, p, q, r)

	def merge(self, list, p, q, r):
		"""
		Função que efectua a junção de duas sublistas de forma ordenada.

		Argumentos:
		list -- lista
		p -- posição inicial da lista
		q -- posição mediana da lista
		r -- tamanho da lista
		"""
		n1 = q - p + 1 # tamanho da lista da esquerda
		n2 = r - q # tamanho da lista da direita

		listLeft=[list[p+i-1] for i in xrange(n1)]  # preenchimento da lista da esquerda
		listRight=[list[q+j] for j in xrange(n2)]	# preenchimento da lista da direita

		listLeft.append(9999)
		listRight.append(9999)
		i=0	# indice para a lista da esquerda
		j=0 # indice para lista da direita
		
		for k in range(p-1,r):
			if listLeft[i] <= listRight[j]:
				list[k] = listLeft[i]
				i=i+1
			else:
				list[k] = listRight[j]
				j=j+1
